'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-05 10:29:11
'''
#
# @lc app=leetcode.cn id=127 lang=python3
#
# [127] 单词接龙
#

# @lc code=start
from typing import List
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        def distance(a, b):
            ans = 0
            for i in range(len(a)):
                if a[i]!=b[i]:
                    ans+=1
            return ans
        wordList.extend([beginWord])
        wordList = list(set(wordList))
        import collections
        store = collections.defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                tmp = word[:i]+'*'+word[i+1:]
                store[tmp].append(word)
                store[word].append(tmp)
            
        word2num = {beginWord:0}
        # print(store)
        q = [beginWord]
        while q:
            tmp = q[0]
            q.pop(0)
            for t in store[tmp]:
                if t not in word2num:
                    q.append(t)
                    word2num[t] = word2num[tmp]+1
                    if t==endWord:
                        return word2num[t]//2+1
        return 0
# @lc code=end

